package datastructure.tree;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class BTNode<E> {
    E data;
    BTNode<E> lchild, rchild;

    public BTNode() {
        lchild = rchild = null;
    }

    public BTNode(E d) {
        this();
        data = d;
    }
}

public class BTreeClass {
    BTNode<Character> b; //root
    String bstr;
    int width[] = new int[10]; //宽度数组
    static String ans = "";//祖先

    public BTreeClass() {
        b = null;
    }

    /*
        创建树
     */
    public void CreateBTree(String str) {
        Stack<BTNode> st = new Stack<BTNode>();
        BTNode<Character> p = null;
        boolean flag = true;
        char ch;
        int i = 0;
        while (i < str.length()) {
            ch = str.charAt(i);
            switch (ch) {
                case '(':
                    st.push(p);
                    flag = true;
                    break;
                case ')':
                    st.pop();
                    break;
                case ',':
                    flag = false;
                    break;
                default:
                    p = new BTNode<Character>(ch);
                    if (b == null) b = p;
                    else {
                        if (flag) {
                            if (!st.empty()) {
                                st.peek().lchild = p;
                            }
                        } else {
                            if (!st.empty()) {
                                st.peek().rchild = p;
                            }
                        }
                    }
                    break;
            }
            i++;
        }
    }

    //打印树
    public void printTree(BTNode bt, int nLayer) {
        if (bt == null)
            return;
        printTree(bt.rchild, nLayer + 1);
        for (int i = 0; i < nLayer; i++)
            System.out.print("  ");
        System.out.println(bt.data);
        printTree(bt.lchild, nLayer + 1);
    }

    //求树中节点数
    public int getNodeCount(BTNode bt) {
        int m, n;
        if (bt == null) return 0;
        m = getNodeCount(bt.lchild);
        n = getNodeCount(bt.rchild);
        return n + m + 1; //加1代表是根节点
    }

    public void getTreeWidth(BTNode bt, int h) {
        if (bt == null) return;
        width[h]++;
        getTreeWidth(bt.lchild, h + 1);
        getTreeWidth(bt.rchild, h + 1);
    }


    /**
     * 计算二叉树的最大宽度（节点数最多的层的节点数量）
     */
    public static int maxWidth(BTNode root) {
        if (root == null) {
            return 0;
        }

        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        int maxWidth = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            // 更新最大宽度
            maxWidth = Math.max(maxWidth, levelSize);

            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                BTNode node = queue.poll();

                // 将子节点加入队列
                if (node.lchild != null) {
                    queue.offer(node.lchild);
                }
                if (node.rchild != null) {
                    queue.offer(node.rchild);
                }
            }
        }

        return maxWidth;
    }

    /**
     * 利用层次遍历寻找x节点的祖先
     * @param bt
     * @param x
     * @return
     */
    public static String ancestorByQueue(BTreeClass bt, char x) {
        ans = "";
        class QNode {
            BTNode<Character> node;
            QNode pre;

            public QNode(BTNode<Character> node, QNode pre) {
                this.node = node;
                this.pre = pre;
            }
        }
        Queue<QNode> queue = new LinkedList<QNode>();
        queue.offer(new QNode(bt.b, null));
        while (!queue.isEmpty()) {
            QNode p = queue.poll();
            if (p.node.data == x) {
                QNode q = p.pre;
                while (q != null) {
                    ans += q.node.data + " ";
                    q = q.pre;
                }
                return ans;
            }

            if (p.node.lchild != null) {
                queue.offer(new QNode(p.node.lchild, p));
            }
            if (p.node.rchild != null) {
                queue.offer(new QNode(p.node.rchild, p));
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        BTreeClass bTreeClass = new BTreeClass();
        String str = "A(B(D(,G)),C(E,F))";
        bTreeClass.CreateBTree(str);
        bTreeClass.printTree(bTreeClass.b, 1);
        System.out.println(bTreeClass.getNodeCount(bTreeClass.b));
        bTreeClass.getTreeWidth(bTreeClass.b, 1);
        System.out.println(Arrays.toString(bTreeClass.width));
        System.out.println(maxWidth(bTreeClass.b));
        String res = ancestorByQueue(bTreeClass, 'D');
        System.out.println(res);
    }
}
